//小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。 
//
// 除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接
//相连的房子在同一天晚上被打劫 ，房屋将自动报警。 
//
// 给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入: root = [3,2,3,null,3,null,1]
//输出: 7 
//解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7 
//
// 示例 2: 
//
// 
//
// 
//输入: root = [3,4,5,1,3,null,1]
//输出: 9
//解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
// 
//
// 
//
// 提示： 
//
// 
//
// 
// 树的节点数在 [1, 10⁴] 范围内 
// 0 <= Node.val <= 10⁴ 
// 
// Related Topics 树 深度优先搜索 动态规划 二叉树 👍 1321 👎 0

package leetcode.editor.cn;
//leetcode submit region begin(Prohibit modification and deletion)

import java.util.HashMap;
import java.util.Map;
import java.util.function.BiFunction;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution337 {
    /**
     * 动态规划
     *
     * @param root
     * @return
     */
    public int rob(TreeNode root) {
        int[] result = robInterval(root);
        return Math.max(result[0],result[1]);
    }

    public int[] robInterval(TreeNode root){
        if(root == null) return new int[2];
//        所以dp数组（dp table）以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，
//        下标为1记录偷该节点所得到的的最大金钱。
        int[] arr = new int[2];
        int[] left = robInterval(root.left);
        int[] right = robInterval(root.right);
        //不拿当前节点
        arr[0] = Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        //拿当前节点
        arr[1] = root.val + left[0] + right[0];
        return arr;
    }

    /**
     * 记忆化 - 解决重复子问题
     * @param root
     * @return
     */
    Map<TreeNode,Integer> map = new HashMap<>();
    public int rob2(TreeNode root) {
        if(root == null) return 0;
        //如果以root为根节点的最大值已经计算过，则不需要重复计算
        if(map.containsKey(root)) return map.get(root);
//        if(root.left == null && root.right == null) return root.val;
//        //偷父节点
//        int val1 = root.val;
//        if(map.containsKey(root)) {
//            val1 = map.get(root);
//        }
        //偷父节点
        int val1 = root.val;
        if(root.left != null) val1+=rob(root.left.left)+rob(root.left.right);
        if(root.right != null) val1+=rob(root.right.left)+rob(root.right.right);
        int val2 = 0;
        val2 += rob(root.left)+rob(root.right);
        int maxValue = Math.max(val1, val2);
        map.put(root, maxValue);
        return maxValue;
    }


    public int rob1(TreeNode root) {
        return traversal(root);
    }

    /**
     * 超时！！
     * 我们计算了root的四个孙子（左右孩子的孩子）为头结点的子树的情况，
     * 又计算了root的左右孩子为头结点的子树的情况，计算左右孩子的时候其实又把孙子计算了一遍
     * @param root
     * @return
     */
    public int traversal(TreeNode root){
        if(root == null) return 0;
        if(root.left==null && root.right==null) return root.val;
        //偷父节点
        int val1 = root.val;
        if(root.left != null) val1+=traversal(root.left.left)+traversal(root.left.right);
        if(root.right != null) val1+=traversal(root.right.left)+traversal(root.right.right);
        //不偷父节点
        int val2 = 0;
        val2+=traversal(root.left)+traversal(root.right);
        return Math.max(val1,val2);
    }

    public static void main(String[] args) {
//        TreeNode root = BinaryTreeFactory.generateBinaryTreeFromArray(new Integer[]{3, 2, 3, null, 3, null, 1});
//        int val = new Solution().rob(root);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
